#include "heap.h"
#define LEFT true
#define RIGHT false

#define LIST_SIZE 2000

Heap::~Heap() {
    //TODO
    //Heap类的析构函数。
    delete []arr;
    arr=NULL;
}

Heap::Heap(Heap &other) {
    //TODO
    //Heap类的拷贝构造函数，需要深度拷贝堆对象。
    this->num=other.num;
    this->arr=new Player_info[LIST_SIZE];
    for(int i=0;i<LIST_SIZE;i++)
    {
        this->arr[i]=other.arr[i];
    }
}

Heap &Heap::operator=(Heap &other) {
    //TODO
    //Heap类的等号赋值操作符，和拷贝构造函数类似。
    this->num=other.num;
    this->arr=new Player_info[LIST_SIZE];
    for(int i=0;i<LIST_SIZE;i++)
    {
        this->arr[i]=other.arr[i];
    }
    return *this;
}

void Heap::heapify_up() {
    //TODO
    //从最后一个元素向上堆化。向上堆化是指自叶子向根部堆化。
    int p=this->num-1;
    if(p<0)return;
    while(1)
    {
        int f=get_father(p);
        if(f<0)break;
        if(this->arr[p]<this->arr[f])
        {
            Player_info t;
            t=this->arr[p];this->arr[p]=this->arr[f];this->arr[f]=t;
            p=f;
        }
        else break;
    }
}

void Heap::heapify_down() {
    //TODO
    //从第一个元素向下堆化。向下堆化是指自根部向叶子堆化。
    int p=0;
    while(1)
    {
        int l=get_child(LEFT,p),r=get_child(RIGHT,p);
        if(l>=num||r<0)return;//左右孩子都不存在，跳出
        if(arr[p]<=arr[l]&&arr[p]<=arr[r])return;
        if(r>=num&&arr[p]>arr[l])//左孩子存在，有孩子不存在，且父大于左子
        {
            //交换父与左子
            Player_info t;
            t=this->arr[p];this->arr[p]=this->arr[l];this->arr[l]=t;
            p=l;
            continue;
        }
        if(r<num&&(arr[p]>arr[r]||arr[p]>arr[l]))//左右子都存在，且父大于两子其一
        {
            if(arr[r]>=arr[l])//右子大于左子，取左子
            {
                //交换父与左子
                Player_info t;
                t=this->arr[p];this->arr[p]=this->arr[l];this->arr[l]=t;
                p=l;
            }
            else
            {
                //交换父与右子
                Player_info t;
                t=this->arr[p];this->arr[p]=this->arr[r];this->arr[r]=t;
                p=r;
            }
            continue;
        }
        return;
    }
}

int Heap::get_child(bool direction, int index) {
    //TODO
    //获得一个下标所对应元素对应的孩子的下标。宏定义了true为LEFT，false为RIGHT。
    if(direction==LEFT)//获取左子
    {
        if(2*index+1<num&&2*index+1>=0)return 2*index+1;
        else return -1;
    }
    else//获取右子
    {
        if(2*index+2<num&&2*index+2>=0)return 2*index+2;
        else return -1;
    }
}

int Heap::get_father(int index) {
    //TODO
    //获得一个下标所对应元素对应的父亲的下标。
    if(index>=num||index<0)return -1;
    if((index-1)/2>=0&&(index-1)/2<num)return (index-1)/2;
    else return -1;
}

int Heap::insert(Player_info &p) {
    //TODO
    //与我们平时的底部插入法不同，这次我们为了实现从数据流中找出前两千个元素的功能，将使用顶部插入法。
    //首先我们比较待插入的元素和顶端元素的大小，因为这是一个小根堆，只要待插入元素比堆顶元素小，
    //说明它比最小元素还小，我们可以舍弃这个元素；反之我们可以把堆顶元素替换为待插入元素，再执行堆化元素整理。
    Player_info* new_play=new Player_info();
    if(&p==new_play)
    {
        delete new_play;
        return -1;
    }
    if(num<LIST_SIZE)//堆未满，使用后插
    {
        arr[num]=p;
        num++;
        heapify_up();
        delete new_play;
        return 0;
    }
    if(p<=arr[0])return -1;
    else
    {
        arr[0]=p;
        heapify_down();
    }
    delete new_play;
    return 0;
}

Player_info *Heap::sort() {
    //TODO
    //你可以自行实现排序算法，但是最后要在函数中返回一个降序排列的数组，长度是 2000。
    //由于插入元素非常多，你可以假设堆已经满了。（这是很重要的提示）
    //上述描述告诉我们排序就可以了
    Player_info* new_play1=new Player_info[LIST_SIZE];
    Player_info* new_play2=new Player_info[LIST_SIZE];
    for(int i=0;i<LIST_SIZE;i++)
    {
        new_play2[i]=arr[i];
    }
    if(num==0)return NULL;
    int len=num;
    while(1)
    {
        if(num==1)break;
        //交换第一个元素与最后一个元素(这里指arr[num-1])
        Player_info t;
        t=*(arr+0);*(arr+0)=*(arr+num-1);*(arr+num-1)=t;
        num--;
        heapify_down();
    }
    num=len;
    for(int i=0;i<LIST_SIZE;i++)
    {
        new_play1[i]=arr[i];
    }
    for(int i=0;i<LIST_SIZE;i++)
    {
        arr[i]=new_play2[i];
    }
    //delete new_play2;
    return new_play1;
}

/*
 =========================================================
 ================ WARNING ===== 警告 ======================
 ===Please Do Not Modify Any of the Following Functions===
 ===================请不要修改以下函数=======================
 =========================================================
 */

int Heap::get_num() const {
    return num;
}

Heap::Heap() {
    num = 0;
    arr = new Player_info[LIST_SIZE];
}

void Heap::print() {
    for (int i = 0; i < num; i++) {
        arr[i].print();
    }
    printf("\nSize of the heap is %d\n", num);
}

Player_info::Player_info() {
    username = std::string("#");
    uid = 0;
    score = 0;
}

Player_info::~Player_info() {

}

Player_info::Player_info(Player_info &other) {
    username = std::string((other.username));
    score = other.score;
    uid = other.uid;
}

Player_info::Player_info(std::string in_name, long in_uid, int in_score) {
    username = std::string(in_name);
    score = in_score;
    uid = in_uid;
}

Player_info &Player_info::operator=(Player_info &other) {
    username = std::string((other.username));
    score = other.score;
    uid = other.uid;
    return *this;
}

int Player_info::get_score() const {
    return score;
}

const std::string &Player_info::get_name() const {
    return username;
}

bool Player_info::operator==(Player_info &other) const {
    if(score == other.score) {
        return true;
    }
    return false;
}

bool Player_info::operator!=(Player_info &other) const {
    if(score == other.score) {
        return false;
    }
    return true;
}

bool Player_info::operator<(Player_info &other) const {
    if(score < other.score) {
        return true;
    }
    return false;
}

bool Player_info::operator<=(Player_info &other) const {
    if(score <= other.score) {
        return true;
    }
    return false;
}

bool Player_info::operator>(Player_info &other) const {
    if(score > other.score) {
        return true;
    }
    return false;
}

bool Player_info::operator>=(Player_info &other) const {
    if(score >= other.score) {
        return true;
    }
    return false;
}

void Player_info::print() {
    printf("[%ld]%s - %d\n", uid, username.c_str(), score);
    return;
}
